Error correcting codes are ubiquitous in communications and data storage systems. Recently considerable interest has grown in a class of codes known as low-density parity-check (LDPC) codes.
LDPC codes are often represented by bipartite graphs, called Tanner graphs, in which one set of nodes, the variable nodes, correspond to bits of the codeword and the other set of nodes, the constraint nodes, sometimes called check nodes, correspond to the set of parity-check constraints which define the code. Edges in the graph connect variable nodes to constraint nodes. A variable node and a constraint node are said to be neighbors if they are connected by an edge in the graph. For simplicity, we generally assume that a pair of nodes is connected by at most one edge.
A bit sequence associated one-to-one with the variable nodes is a codeword of the code if and only if, for each constraint node, the bits neighboring the constraint (via their association with variable nodes) sum to zero modulo two, i.e., they comprise an even number of ones.
In some cases a codeword may be punctured. This refers to the act of removing or puncturing certain bits from the codeword and not actually transmitting them. When encoding an LDPC code, however, bits which are to be punctured are still determined. Thus, puncturing has little or no impact on the encoding process. For this reason we will ignore the possibility of puncturing in the remainder of this application.
The decoders and decoding algorithms used to decode LDPC codewords operate by exchanging messages within the graph along the edges and updating these messages by performing computations at the nodes based on the incoming messages. Such algorithms are generally referred to as message passing algorithms. Each variable node in the graph is initially provided with a soft bit, termed a received value, that indicates an estimate of the associated bit's value as determined by observations from, e.g., the communications channel. The encoding process, which is the focus of this application, also operates in part along the edges of the graph but the connection is less precise.
The number of edges attached to a node, i.e., a variable node or constraint node, is referred to as the degree of the node. A regular graph or code is one for which all variable nodes have the same degree, j say, and all constraint nodes have the same degree, k say. In this case we say that the code is a (j,k) regular code. These codes were originally invented by Gallager (1961). In contrast to a “regular” code, an irregular code has constraint nodes and/or variable nodes of differing degrees. For example, some variable nodes may be of degree 4, others of degree 3 and still others of degree 2.
While irregular codes can be more complicated to represent and/or implement, it has been shown that irregular LDPC codes can provide superior error correction/detection performance when compared to regular LDPC codes.
While encoding efficiency and high data rates are important, for an encoding and/or decoding system to be practical for use in a wide range of devices, e.g., consumer devices, it is important that the encoders and/or decoders be capable of being implemented at reasonable cost. Accordingly, the ability to efficiently implement encoding/decoding schemes used for error correction and/or detection purposes, e.g., in terms of hardware costs, can be important.
An exemplary bipartite graph 100 determining a (3,6) regular LDPC code of length ten and rate one-half is shown in FIG. 1. Length ten indicates that there are ten variable nodes V1-V10, each identified with one bit of the codeword X1-X10. The set of variable nodes V1-V10 is generally identified in FIG. 1 by reference numeral 102. Rate one half indicates that there are half as many check nodes as variable nodes, i.e., there are five check nodes C1-C5 identified by reference numeral 106. Rate one half further indicates that the five constraints are linearly independent, as discussed below.
While FIG. 1 illustrates the graph associated with a code of length 10, it can be appreciated that representing the graph for a codeword of length 1000 would be 100 times more complicated.
An alternative to the Tanner graph representation of LDPC codes is the parity check matrix representation such as that shown in FIG. 2. In this representation of a code, the matrix H 202, commonly referred to as the parity check matrix, includes the relevant edge connection, variable node and constraint node information. In the matrix H, each column corresponds to one of the variable nodes while each row corresponds to one of the constraint nodes. Since there are 10 variable nodes and 5 constraint nodes in the exemplary code, the matrix H includes 10 columns and 5 rows. The entry of the matrix corresponding to a particular variable node and a particular constraint node is set to 1 if an edge is present in the graph, i.e., if the two nodes are neighbors, otherwise it is set to 0. For example, since variable node V1 is connected to constraint node C1 by an edge, a one is located in the uppermost lefthand corner of the matrix 202. However, variable node V5 is not connected to constraint node C1 so a 0 is positioned in the fifth position of the first row of matrix 202 indicating that the corresponding variable and constraint nodes are not connected. We say that the constraints are linearly independent if the rows of H are linearly independent vectors over GF[2].
In the case of a matrix representation, the codeword X which is to be transmitted can be represented as a vector 206 which includes the bits X1-Xn of the codeword to be processed. A bit sequence X1-Xn is a codeword if and only if the product of the matrix 206 and 202 is equal to zero, that is: Hx=0.